package ljl.codetop;

/**
 * 题目说了数字各不相同，所以不用考虑重复的问题了
 */
public class _33_search_spin_arr {

    /**
     * 我只知道是二分
     * 450123
     * 345012
     *
     * 它有一个问题，玩家可能认为和左边右边比都可以，其实不然，因为求中点时会向下取整，所以肯定是不一样的
     *
     * 操他妈当成"旋转数组最小值了"，这道题不是
     * 这道题是搜索旋转数组里的某个值，不是最小值
     *
     * 虽然错了很多次，但是最终过了，还是不错的，看来代码是讲逻辑的，不会无理取闹
     */
    static class tryout {
        public int search(int[] nums, int target) {
            int l = 0, r = nums.length - 1;
            while (l <= r) {
                int mid = (l + r) >>> 1;
                if (target == nums[mid])
                    return mid;
                if (nums[mid] <= nums[r]) {
                    if (target > nums[mid] && target <= nums[r]) {
                        l = mid + 1;
                    } else {
                        r = mid - 1;
                    }
                } else {
                    if (target >= nums[l] && target < nums[mid]) {
                        r = mid - 1;
                    } else {
                        l = mid + 1;
                    }
                }
            }
            return -1;
        }
    }

    static class off1 {

        public int search(int[] nums, int target) {
            int n = nums.length;
            if (n == 0) {
                return -1;
            }
            if (n == 1) {
                return nums[0] == target ? 0 : -1;
            }
            int l = 0, r = n - 1;
            while (l <= r) {
                int mid = (l + r) / 2;
                if (nums[mid] == target) {
                    return mid;
                }
                if (nums[l] <= nums[mid]) {
                    if (nums[l] <= target && target < nums[mid]) {
                        r = mid - 1;
                    } else {
                        l = mid + 1;
                    }
                } else {
                    if (nums[mid] < target && target <= nums[r]) {
                        l = mid + 1;
                    } else {
                        r = mid - 1;
                    }
                }
            }
            return -1;
        }

    }
}
